#include <iostream>
// TIP 要<b>Run</b>代码，请按 <shortcut actionId="Run"/> 或点击装订区域中的 <icon src="AllIcons.Actions.Execute"/> 图标。
using namespace std;

int func1() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if(!(cin >> T)) return 0;
    while (T--) {
        int n; long long m;
        cin >> n >> m;
        vector<long long> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];

        int base = 0;
        // Kadane
        long long cur = 0, best = 0;
        for (int i = 0; i < n; ++i) {
            if (a[i] >= m) base++;

            long long ci = 0;
            if (a[i] <  m) ci = +1;
            else if (a[i] > m) ci = -1;
            else ci = 0;

            cur = max(0LL, cur + ci);
            best = max(best, cur);
        }
        cout << (base + best) << "\n";
    }
    return 0;
}


int func2() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    // 所有子数组总数
    long long total = 1LL * n * (n + 1) / 2;

    // 统计不含 0 的子数组个数 = 各个“连续非零段”的子数组数之和
    long long bad = 0;
    long long len = 0;  // 当前连续非零段长度
    for (int i = 0; i < n; ++i) {
        if (a[i] != 0) {
            ++len;
        } else {
            bad += len * (len + 1) / 2;
            len = 0;
        }
    }
    bad += len * (len + 1) / 2; // 收尾

    cout << (total - bad) << "\n";
    return 0;
}


const long long MOD = 998244353;

// 线性DP：返回 F(n) (n>=0), F(0)=0, F(1)=1
long long fib_linear(long long n){
    if(n==0) return 0;
    long long a = 0, b = 1; // F(0), F(1)
    for(long long i = 2; i <= n; ++i){
        long long c = (a + b) % MOD; // F(i)=F(i-1)+F(i-2)
        a = b;
        b = c;
    }
    return (n==1 ? 1 : b % MOD);
}

int func3(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    if(!(cin >> T)) return 0;
    while(T--){
        long long k;
        cin >> k;
        if(k == 1) cout << 1 << "\n";
        else       cout << fib_linear(k - 1) << "\n"; // 答案 = F_{k-1}
    }
    return 0;
}